package com.tarry.spare.array;

/**
 *  稀疏数组示例
 */
public class SparseArray {

    /**
     * 将稀疏数组转换为普通数组
     * @param array
     * @return
     */
    public static int[][] toArray(int[][] array){
        int[][] result = new int[array[0][0]][array[0][1]];
        for(int i = 1 ; i < array.length ; i ++){
            result[array[i][0]][array[i][1]] = array[i][2];
        }
        return  result;
    }

    /**
     *  统计普通数组中值不为0的个数
     * @param array
     * @return
     */
    public static int getNonZero(int[][] array){
        int sum = 0;
        for (int i = 0 ; i< array.length; i++){ //计算数组非零个数
            for (int j = 0; j < array[i].length ; j ++){
                if(array[i][j] != 0){
                    sum++;
                }
            }
        }
        return sum;
    }

    /**
     *  构建稀疏数组
     * @param array
     * @return
     */
    public static int[][] createSparseArray(int[][] array){
        int sum = SparseArray.getNonZero(array);
        //创建稀疏数组
        int[][] spareArray = new int[sum + 1][3];
        //记录原始数组的大小，以及非零个数
        spareArray[0][0] = array.length; //记录数组行
        spareArray[0][1] = array[0].length; //记录数组列
        spareArray[0][2] = sum;
        return spareArray;
    }

    /**
     *  将普通数组转换为稀疏数组
     * @param array
     * @return
     */
    public static int[][] toSparseArray(int[][] array){
        //创建稀疏数组
        int[][] spareArray = SparseArray.createSparseArray(array);
        int rowIndex = 0; //行下标
        for (int i = 0 ; i < array.length ; i++){
            for (int j = 0 ; j < array[i].length ; j++){
                if(array[i][j] != 0){
                    rowIndex ++ ;
                    spareArray[rowIndex][0] = i; // 记录原始数组的行标
                    spareArray[rowIndex][1] = j; // 记录原始数组的列标
                    spareArray[rowIndex][2] = array[i][j]; // 记录原始数组的值
                }
            }
        }
        return spareArray;
    }
}
